package com.cet.qz.unit01.chapter1_3;

import edu.princeton.cs.algs4.StdIn;

/**
 * @program: algorithm
 * @description: 括号匹配  ()[]{}
 * @author: 陈恩涛
 * @create: 2021-04-01 21:33
 **/
public class Parenthese {

    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();

        //括号表达式为空则合法
        if (expression.length() == 0) {
            return true;
        }

        //括号都是成对出现
        if (expression.length() % 2 != 0) {
            return false;
        }

        for (int i = 0; i < expression.length(); i++) {

            char kh = expression.charAt(i);

            //遇到左括号则入栈
            if (kh == '(' || kh == '[' || kh == '{') {
                stack.push(kh);
            } else if (stack.isEmpty()) {
                return false;
            }

            if (kh == ')' && stack.pop() != '(') {
                return false;
            }

            if (kh == ']' && stack.pop() != '[') {
                return false;
            }

            if (kh == '}' && stack.pop() != '{') {
                return false;
            }
        }
        //最终栈空则括号表达式合法
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println("请输入一个只包含：'('、')'、'['、']'、'{'、'}'的表达式:");
        String expression = StdIn.readString();
        boolean isLegal = isBalanced(expression);
        System.out.println("输入的括号表达式"+(isLegal?"合法":"不合法"));
    }
}
